#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int fib(int n) {
        if (n == 0) { return 0; }
        if (n == 1) { return 1; }
        return fib(n - 1) + fib(n - 2);
    }
};
class Solution {
public:
    int fib(int n) {
        if (n <= 0) { return n; }
        int dp[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};
class Solution {
public:
    int fib(int n) {
        if (n <= 1) { return n; }
        int prev0 = 0;
        int prev1 = 1;
        int current = 0;
        for (int i = 2; i <= n; i++) {
            current = prev0 + prev1;
            prev0 = prev1;
            prev1 = current;
        }
        return current;
    }
};
class Solution {
public:
    int fib(int n) {
        vector<int>memo(n + 1, -1);
        return helper(n, memo);
    }
private:
    int helper(int n, vector<int>& memo) {
        if (n <= 1) { return n; }
        if (memo[n] != -1) { return memo[n]; }
        memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
        return memo[n];
    }
};